package Link;

import java.util.HashMap;
import java.util.Map;

public class leet_142 {
}

class Solution_142 {
    /**
     * 利用hash来解决问题
     * @param head
     * @return
     */
    public ListNode detectCycleHash(ListNode head) {
        if(head ==null || head.next==null){return null;}
        // hash 法
        Map<ListNode, Integer> hashMap = new HashMap<>();
        ListNode pre = head;
        while(pre!=null){
            if(hashMap.containsKey(pre)){
                return pre;
            }
            hashMap.put(pre, 1);
            pre = pre.next;
        }
        return null;
    }

    /**
     * 1.环表 分为2个部分 a：头结点到环口 e:环口到环口
     * 2.设置2个指针，快慢指针quick 与 slow。quick一次2步 slow一次一步
     * 3.此时我们的快慢指针必定会相遇 此时点为b 记为 e=b+c
     * 4.得出公式  quick = 2slow;   n(b+c)+b+a = 2(a+b);
     * 5.化减 a=n(b+c)-b ==>     a=(n-1)(b+c)+c
     * 6.当相遇时，设置一个新指针 pre 从头指针开始走。
     * 7.当pre 与 slow相遇时 代表 slow 需要走c+(n-1)(b+C) 代表 pre 刚好走a
     * 8.二者相遇在环开始的位置
     * @param head
     * @return
     */
    public ListNode detectCycleSlow(ListNode head){
        if(head==null || head.next==null || head.next.next==null){return null;}
        // 快慢指针一定是一起走的
        ListNode quick = head.next.next;
        ListNode slow = head.next;

        while(quick!=slow){
            if(quick==null || quick.next==null){
                // 能跳出循环就代表他们2个没有相遇
                // 所有没有环
                return null;
            }
            slow = slow.next;
            quick = quick.next.next;
        }

        // 相遇
        ListNode pre = head;
        while(pre!=slow){
            slow = slow.next;
            pre = pre.next;
        }
        return pre;
    }
}

